package quoridor;

import java.util.ArrayList;

public class QuoridorBoard implements Board
{
   private boolean[][] vertical;
   private boolean[][] horizontal;
   private Coordinate blackLocation;
   private Coordinate whiteLocation;
   private int blackFences;
   private int whiteFences;
   private ArrayList<QuoridorMove> history;
   private int historyTracker;
   private int undoneStreak;
   // length of the board
   private static int length = 9;
   private static int totalFences = 10;
   
   public QuoridorBoard()
   {
      vertical = new boolean[length-1][length];
      horizontal = new boolean[length-1][length];
      blackLocation = new QuoridorCoordinate (length-1,length/2);
      whiteLocation = new QuoridorCoordinate (0,length/2);
      blackFences = totalFences;
      whiteFences = totalFences;
      history = new ArrayList<QuoridorMove>();
      historyTracker = 0;
      undoneStreak = 0;
   }
   
   public QuoridorBoard(String gameHistory) {
     vertical = new boolean[length-1][length];
     horizontal = new boolean[length-1][length];
      blackLocation = new QuoridorCoordinate (length-1,length/2);
      whiteLocation = new QuoridorCoordinate (0,length/2);
      blackFences = totalFences;
      whiteFences = totalFences;
      history = new ArrayList<QuoridorMove>();
      historyTracker = 0;
      undoneStreak = 0;
     
      
     Converter stringConverter = new Converter(gameHistory);
     Move nextMove;
     
     while ((nextMove = stringConverter.getNextMove()) != null) {
         assert(validateMove(nextMove));
         makeMove(nextMove);
     }
     
   }
   
   @Override
   public Coordinate getPlayerLocation(PlayerColour playerColour)
   { 
      if (playerColour.equals(PlayerColour.BLACK))
         return blackLocation;
      else if (playerColour.equals(PlayerColour.WHITE))
         return whiteLocation;
      else
      {
         throw new IllegalStateException("not a valid PlayerColour");
      }
   }

   // check if a coordinate is on the board
   private boolean isLocationOnBoard(Coordinate dest)
   {
      if (dest.getColumn() < 0 || dest.getColumn() >= length)
      {
         return false;
      }
      if (dest.getRow() < 0 || dest.getRow() >= length)
      {
         return false;
      }
      return true;
   }
   
   @Override
   public boolean validateMove (Move newMove)
   {
      QuoridorMove move = (QuoridorMove) newMove;
      int type = move.getType();
      Coordinate dest = move.getCoordinate();
      if (!isLocationOnBoard(dest))
         return false;
      switch (type)
      {
      // Move is changing the position of a piece
          case 0:
            Coordinate src = this.getPlayerLocation(move.getPlayer());
            Coordinate other;
            if(move.getPlayer().equals(PlayerColour.BLACK))
               other = getPlayerLocation(PlayerColour.WHITE);
            else
               other = getPlayerLocation(PlayerColour.BLACK);
            if (Math.abs(src.getColumn() - dest.getColumn()) +
                  Math.abs(src.getRow() - dest.getRow()) > 2)
            {
               return false;
            }
            // Check if the move will land on the other player
            if (dest.getRow() == other.getRow() && 
                  dest.getColumn() == other.getColumn())
               return false;
            
            //Check if move is horizontal
            if (src.getRow() == dest.getRow() &&
                  Math.abs(src.getColumn()-dest.getColumn()) == 1)
            {
               if ((src.getColumn() - dest.getColumn() == 1) &&
                     !vertical[dest.getColumn()][src.getRow()])
               {
                  return true;
               }
               else if ((dest.getColumn() - src.getColumn() == 1) &&
                     !vertical[src.getColumn()][src.getRow()])
               {
                  return true;
               }
               return false;
            }
            //Check if move is vertical
            else if (src.getColumn() == dest.getColumn() &&
                  Math.abs(src.getRow() - dest.getRow()) == 1)
            {
               if ((src.getRow() - dest.getRow() == 1) &&
                     !horizontal[dest.getRow()][src.getColumn()])
               {
                  return true;
               }
               else if ((src.getRow() - dest.getRow() == -1) &&
                     !horizontal[src.getRow()][src.getColumn()])
               {
                  return true;
               }
               return false;
            }
            //Check if move is diagonal and other player's piece is adjacent
            else if (Math.abs(src.getColumn()-dest.getColumn()) == 1 && 
                  Math.abs(src.getRow()-dest.getRow()) == 1)
            {
               if (src.getRow() == other.getRow() &&
                     Math.abs(src.getColumn() - other.getColumn()) == 1)
               {
                  if(src.getColumn() - other.getColumn() == 1)
                  {
                     if (vertical[src.getColumn()-1][src.getRow()] ||
                           (other.getColumn() != 0 && 
                                 !vertical[other.getColumn()-1][other.getRow()]))
                        return false;
                  }
                  else if (src.getColumn() - other.getColumn() == -1)
                  {
                     if (vertical[src.getColumn()][src.getRow()] ||
                           (other.getColumn() != length-1 && 
                                 !vertical[other.getColumn()][other.getRow()]))
                        return false;
                  }
                  
                  if (other.getColumn() == dest.getColumn() &&
                        other.getRow() - dest.getRow() == 1)
                  {
                     if (!horizontal[other.getRow()-1][other.getColumn()])
                        return true;
                  }
                  else if (other.getColumn() == dest.getColumn() &&
                        other.getRow() - dest.getRow() == -1)
                  {
                     if (!horizontal[other.getRow()][other.getColumn()])
                        return true;
                  }
                  return false;
               }
               else if (src.getColumn() == other.getColumn() &&
                     Math.abs(src.getRow() - other.getRow()) == 1)
               {
                  if(src.getRow() - other.getRow() == 1)
                  {
                     if (horizontal[src.getRow()-1][src.getColumn()] ||
                           (other.getRow() != 0 && 
                                 !horizontal[other.getRow()-1][other.getColumn()]))
                        return false;
                  }
                  else if (src.getRow() - other.getRow() == -1)
                  {
                     if (horizontal[src.getRow()][src.getColumn()] ||
                           (other.getRow() != length-1 && 
                                 !horizontal[other.getRow()][other.getColumn()]))
                        return false;
                  }
                  
                  if (other.getRow() == dest.getRow() &&
                        other.getColumn() - dest.getColumn() == 1)
                  {
                     if (!vertical[other.getColumn()-1][other.getRow()])
                        return true;
                  }
                  else if (other.getRow() == dest.getRow() &&
                        other.getColumn() - dest.getColumn() == -1)
                  {
                     if (!vertical[other.getColumn()][other.getRow()])
                        return true;
                  }
                  return false;
               }
               return false;
            }
            // Check if move is a hop-over the opponent
            else if ((src.getRow() == dest.getRow() &&
                  Math.abs(src.getColumn() - dest.getColumn()) == 2) ||
                  (src.getColumn() == dest.getColumn() && 
                  Math.abs(src.getRow() - dest.getRow()) == 2))
                  {
                     //Horizontal hop
                     if (src.getRow() == other.getRow())
                     {
                        if (src.getColumn() - other.getColumn() == 1 &&
                              src.getColumn() - dest.getColumn() == 2)
                        {
                           if (!vertical[src.getColumn()-1][src.getRow()] && 
                                 !vertical[src.getColumn()-2][src.getRow()])
                              return true;
                           else
                              return false;
                        }
                        if (src.getColumn() - other.getColumn() == -1 &&
                              src.getColumn() - dest.getColumn() == -2)
                        {
                           if (!vertical[src.getColumn()][src.getRow()] && 
                                 !vertical[src.getColumn()+1][src.getRow()])
                              return true;
                           else
                              return false;
                        }
                        return false;
                     }
                     // Vertical hop
                     else if (src.getColumn() == other.getColumn())
                     {
                        if (src.getRow() - other.getRow() == 1 &&
                              src.getRow() - dest.getRow() == 2)
                        {
                           if (!horizontal[src.getRow()-1][src.getColumn()] &&
                                 !horizontal[src.getRow()-2][src.getColumn()])
                              return true;
                           else
                              return false;
                        }
                        else if (src.getRow() - other.getRow() == -1 &&
                              src.getRow() - dest.getRow() == -2)
                        {
                           if (!horizontal[src.getRow()][src.getColumn()] &&
                                 !horizontal[src.getRow()+1][src.getColumn()])
                              return true;
                           else
                              return false;
                        }
                        return false;
                     }
                  }
               return false;
      // Move is placing a fence
      case 1:case 2:
         if (dest.getRow() > 7 ||
               dest.getColumn() > 7)
            return false;
         {
            if (this.getFenceNum(move.getPlayer()) < 1)
               return false;
            if (dest.getRow() > length -2 || dest.getColumn() > length -2)
               return false;
            // Check if the placing is vertical
            if (type == 1)
            {
               if (vertical[dest.getColumn()][dest.getRow()] || 
                     vertical[dest.getColumn()][dest.getRow()+1])
               {
                  return false;
               }
               else if (horizontal[dest.getRow()][dest.getColumn()] && 
                     horizontal[dest.getRow()][dest.getColumn()+1])
               {
                  return false;
               }
               return isPath(move);
               
            }
            // Check if the placing is horizontal
            else
            {
               if (horizontal[dest.getRow()][dest.getColumn()] ||
                     horizontal[dest.getRow()][dest.getColumn()+1])
               {
                  return false;
               }
               else if (vertical[dest.getColumn()][dest.getRow()] &&
                     vertical[dest.getColumn()][dest.getRow()+1])
               {
                  return false;
               }
               return isPath(move);
            }
         }
      }
      return false;
   }
   
   public int getFenceNum(PlayerColour player)
   {
      if (player.equals(PlayerColour.BLACK))
         return blackFences;
      else if (player.equals(PlayerColour.WHITE))
         return whiteFences;
      else
      {
         throw new IllegalStateException("not a valid PlayerColour");
      }
   }

   private boolean isPath(Move newMove)
   {
      QuoridorMove move = (QuoridorMove) newMove;
      Coordinate target = move.getCoordinate();
      if (move.getType() == 1)
      {
         vertical[target.getColumn()][target.getRow()] = true;
         vertical[target.getColumn()][target.getRow()+1] = true;
      }
      else if (move.getType() == 2)
      {
         horizontal[target.getRow()][target.getColumn()] = true;
         horizontal[target.getRow()][target.getColumn()+1] = true;
      }
      boolean[][] visits = new boolean[length][length];
      int maxCounter = 0;
      while (!hasReachedRow(visits, 0) && maxCounter < length*length)
      {
         for (int i = 0; i < visits.length; i++)
         {
            for (int j = 0; j < visits[i].length; j++)
            {
               if (visits[i][j]);
               else if ((Math.abs(blackLocation.getRow() - i)) +
                     (Math.abs(blackLocation.getColumn() - j)) <= maxCounter)
               {
                  if (blackLocation.getRow() == i &&
                        blackLocation.getColumn() == j)
                  {
                     visits[i][j] = true;
                  }
                  if (j > 0)
                  {
                     if (visits[i][j-1] && !vertical[j-1][i])
                     {
                        visits[i][j] = true;
                     }
                  }
                  if (j < length-1)
                  {
                     if (visits[i][j+1] && !vertical[j][i])
                     {
                        visits[i][j] = true;
                     }
                  }
                  if (i > 0)
                  {
                     if (visits[i-1][j] && !horizontal[i-1][j])
                     {
                        visits[i][j] = true;
                     }
                  }
                  if (i < length-1)
                  {
                     if (visits[i+1][j] && !horizontal[i][j])
                     {
                        visits[i][j] = true;
                     }
                  }
               }
            }
         }
         maxCounter++;
      }
      boolean blackHasPath = false;
      for (int i = 0; i < length; i++)
      {
         if (visits[0][i])
            blackHasPath = true;
      }
      
      visits = new boolean[length][length];
      
      maxCounter = 0;
      while (!hasReachedRow(visits, length-1) && maxCounter < 64)
      {
         for (int i = 0; i < visits.length; i++)
         {
            for (int j = 0; j < visits[i].length; j++)
            {
               if (visits[i][j]);
               else if ((Math.abs(whiteLocation.getRow() - i)) +
                     (Math.abs(whiteLocation.getColumn() - j)) <= maxCounter)
               {
                  if (whiteLocation.getRow() == i &&
                        whiteLocation.getColumn() == j)
                  {
                     visits[i][j] = true;
                  }
                  if (j > 0)
                  {
                     if (visits[i][j-1] && !vertical[j-1][i])
                     {
                        visits[i][j] = true;
                     }
                  }
                  if (j < length-1)
                  {
                     if (visits[i][j+1] && !vertical[j][i])
                     {
                        visits[i][j] = true;
                     }
                  }
                  if (i > 0)
                  {
                     if (visits[i-1][j] && !horizontal[i-1][j])
                     {
                        visits[i][j] = true;
                     }
                  }
                  if (i < length-1)
                  {
                     if (visits[i+1][j] && !horizontal[i][j])
                     {
                        visits[i][j] = true;
                     }
                  }
               }
            }
         }
         maxCounter++;
      }
      boolean whiteHasPath = false;
      for (int i = 0; i < length; i++)
      {
         if (visits[length-1][i])
            whiteHasPath = true;
      }
      if (move.getType() == 1)
      {
         vertical[target.getColumn()][target.getRow()] = false;
         vertical[target.getColumn()][target.getRow()+1] = false;
      }
      else if (move.getType() == 2)
      {
         horizontal[target.getRow()][target.getColumn()] = false;
         horizontal[target.getRow()][target.getColumn()+1] = false;
      }
      return (blackHasPath && whiteHasPath);
   }
   
   private boolean isAllTrue(boolean[][] array)
   {
      boolean toReturn = true;
      for (int i = 0; i < array.length; i++)
      {
         for (int j = 0; j < array[i].length; j++)
         {
            if (!array[i][j])
               toReturn = false;
         }
      }
      return toReturn;
   }
   
   private boolean hasReachedRow(boolean[][] array, int row)
   {
      for (int i = 0; i < array[row].length; i++)
      {
         if (array[row][i])
            return true;
      }
      return false;
   }
   
   @Override
   public boolean isOver() 
   {
      if (whiteLocation.getRow() == length-1 ||
            blackLocation.getRow() == 0)
         return true;
      else
         return false;
   }
   
   @Override
   public boolean makeMove(Move nextMove) 
   {
      QuoridorMove move = (QuoridorMove) nextMove;
      addMoveToHistory(move);
      undoneStreak = 0;
      
      return enactMove(move);
   }
   
   private void addMoveToHistory(QuoridorMove move)
   {
      if (historyTracker == history.size())
         history.add(move);
      else
         history.set(historyTracker, move);
      historyTracker++;
   }
   
   private boolean enactMove(QuoridorMove move)
   {
      Coordinate target = move.getCoordinate();
      
      if (move.getType() == 0)
      {
         if (move.getPlayer() == PlayerColour.WHITE)
         {
            whiteLocation = target;
         }
         else if (move.getPlayer() == PlayerColour.BLACK)
         {
            blackLocation = target;
         }
         else
         {
            return false;
         }
         return true;
      }
      else if (move.getType() == 1 || 
            move.getType() == 2)
      {
         if (move.getPlayer() == PlayerColour.WHITE)
         {
            whiteFences--;
         }
         else if (move.getPlayer() == PlayerColour.BLACK)
         {
            blackFences--;
         }
         else
         {
            return false;
         }
         if (move.getType() == 1)
         {
            vertical[target.getColumn()][target.getRow()] = true;
            vertical[target.getColumn()][target.getRow()+1] = true;
         }
         else
         {
            horizontal[target.getRow()][target.getColumn()] = true;
            horizontal[target.getRow()][target.getColumn()+1] = true;
         }
         return true;
      }
      return false;
   }
   
   
   @Override
   public String getHistory()
   {
      StringBuilder builder = new StringBuilder();
      for (int i = 0; i < historyTracker; i++)
      {
         builder.append(Converter.moveToString(history.get(i)));
         if (i < historyTracker-1)
            builder.append(' ');
      }
      return builder.toString();
   }
   
   @Override
   public PlayerColour currentPlayer()
   {
      if (historyTracker%2 == 0) {
         return PlayerColour.BLACK;
      } else {
         return PlayerColour.WHITE;
      }
   }
   
   @Override
   public boolean[][] getHorizontalFences()
   {
      return horizontal;
   }
   
   @Override
   public boolean[][] getVerticalFences()
   {
      return vertical;
   }
   
   @Override
   public boolean redoMove()
   {
      if (undoneStreak < 2)
         return false;
      else
      {
         redoSingleMove();
         redoSingleMove();
         return true;
      }
   }
   
   private boolean redoSingleMove()
   {
      if (undoneStreak < 1)
         return false;
      QuoridorMove toRedo = history.get(historyTracker);
      undoneStreak--;
      historyTracker++;
      return enactMove(toRedo);
   }
   
   @Override
   public boolean undoMove()
   {
      if (historyTracker > 1)
      {
         undoSingleMove();
         undoSingleMove();
         return true;
      }
      else
         return false;
     
   }
   
   public boolean undoSingleMove()
   {
      historyTracker--;
      undoneStreak++;
      QuoridorMove toUndo = history.get(historyTracker);
      Coordinate target = toUndo.getCoordinate();
      if (toUndo.getType() == 0)
      {
         Coordinate old = null;
         if (historyTracker > 1)
         {
            old = history.get(historyTracker-2).getCoordinate();
         }
         else if (toUndo.getPlayer() == PlayerColour.BLACK)
            old = new QuoridorCoordinate(length-1, length/2);
         else if (toUndo.getPlayer() == PlayerColour.WHITE)
            old = new QuoridorCoordinate(0, length/2);
         if (toUndo.getPlayer() == PlayerColour.BLACK)
         {
            blackLocation = old;
            return true;
         }
         else if (toUndo.getPlayer() == PlayerColour.WHITE)
         {
            whiteLocation = old;
            return true;
         }
      }
      else if (toUndo.getType() == 1)
      {
         vertical[target.getColumn()][target.getRow()] = false;
         vertical[target.getColumn()][target.getRow()+1] = false;
         
      }
      else if (toUndo.getType() == 2)
      {
         horizontal[target.getRow()][target.getColumn()] = false;
         horizontal[target.getRow()][target.getColumn()+1] = false;
      }
      if (toUndo.getType() == 1 ||
            toUndo.getType() == 2)
      {
         if (toUndo.getPlayer() == PlayerColour.WHITE)
         {
            whiteFences++;
         }
         else if (toUndo.getPlayer() == PlayerColour.BLACK)
         {
            blackFences++;
         }
         return true;
      }
      return false;
   }
   
   @Override
   public PlayerColour opposingPlayer()
   {
      if (historyTracker == 0)
         return PlayerColour.WHITE;
      else
         return history.get(historyTracker-1).getPlayer();
   }
   
   @Override
   public int distanceToFinish(PlayerColour player)
   {
      Coordinate other;
      if (player.equals(PlayerColour.WHITE))
      {
         other = getPlayerLocation(PlayerColour.BLACK);
      }
      else
         other = getPlayerLocation(PlayerColour.WHITE);
      boolean visits[][] = new boolean[length][length];
      int cost[][] = new int[length][length];
      Coordinate src = getPlayerLocation(player);
      visits[src.getRow()][src.getColumn()] = true;
      if (Math.abs(src.getRow() - other.getRow()) +
            Math.abs(src.getColumn() - other.getColumn()) == 1)
      {
         if (src.getRow() == other.getRow())
         {
            if (src.getColumn()-other.getColumn() == 1 &&
                  !vertical[src.getColumn()-1][src.getRow()])
            {
               if (src.getColumn() > 1 &&
                     !vertical[src.getColumn()-2][src.getRow()])
               {
                  visits[src.getRow()][src.getColumn()-2] = true;
                  cost[src.getRow()][src.getColumn()-2] = 1;
               }
               
            }
            else if (src.getColumn()-other.getColumn() == -1 &&
                  !vertical[src.getColumn()][src.getRow()])
            {
               if (src.getColumn() < length-2 &&
                     !vertical[src.getColumn()+1][src.getRow()])
               {
                  visits[src.getRow()][src.getColumn()+2] = true;
                  cost[src.getRow()][src.getColumn()+2] = 1;
               }
            }
         }
         else if (src.getColumn() == other.getColumn())
         {
            if (src.getRow()-other.getRow() == 1 &&
                  !horizontal[src.getRow()-1][src.getColumn()])
            {
               if (src.getRow() > 1 &&
                     !horizontal[src.getRow()-2][src.getColumn()])
               {
                  visits[src.getRow()-2][src.getColumn()] = true;
                  cost[src.getRow()-2][src.getColumn()] = 1;
               }
            }
            else if (src.getRow()-other.getRow() == -1 &&
                  !horizontal[src.getRow()][src.getColumn()])
            {
               if (src.getRow() < length-2 &&
                     !horizontal[src.getRow()+1][src.getColumn()])
               {
                  visits[src.getRow()+2][src.getColumn()] = true;
                  cost[src.getRow()+2][src.getColumn()] = 1;
               }
            }
         }
      }
      
      int maxCounter = 64;
      while (!isAllTrue(visits) && maxCounter > 0)
      {
         for (int i = 0; i < length; i++)
         {
            for (int j = 0; j < length; j++)
            {
               boolean hasVisited = false;
               int minCost = Integer.MAX_VALUE;
               if (!visits[i][j])
               {
                  if (j > 0 && visits[i][j-1] &&
                        !vertical[j-1][i] &&
                        cost[i][j-1] < minCost)
                  {
                     hasVisited = true;
                     minCost = cost[i][j-1];
                  }
                  if (j < length-1 && visits[i][j+1] &&
                        !vertical[j][i] &&
                        cost[i][j+1] < minCost)
                  {
                     hasVisited = true;
                     minCost = cost[i][j+1];
                  }
                  if (i > 0 && visits[i-1][j] &&
                        !horizontal[i-1][j] &&
                        cost[i-1][j] < minCost)
                  {
                     hasVisited = true;
                     minCost = cost[i-1][j];
                  }
                  if (i < length-1 && visits[i+1][j] &&
                        !horizontal[i][j] &&
                        cost[i+1][j] < minCost)
                  {
                     hasVisited = true;
                     minCost = cost[i+1][j];
                  }
                  if (hasVisited)
                  {
                     visits[i][j] = true;
                     cost[i][j] = minCost+1;
                  }
               }
            }
         }
         maxCounter--;
      }
      int distance = Integer.MAX_VALUE;
      if (player.equals(PlayerColour.BLACK))
      {
         for (int i = 0; i < length; i++)
         {
            if (cost[0][i] < distance && visits[0][i])
               distance = cost[0][i];
         }
      }
      else
      {
         for (int i = 0; i < length; i++)
         {
            if (cost[length-1][i] < distance && visits[length-1][i])
               distance = cost[length-1][i];
         }
      }
      return distance;
   }
}
